package main

import (
	"fmt"
)

type CmpFunc func(i, j int) bool
type HeapEler interface {
	Value() int
}
type Heap struct {
	list      []int
	isMinHeap bool
}

/**
 * @description: 压入
 * @param {int} x
 * @return {*}
 */
func (h *Heap) Push(x int) {
	len := len(h.list)
	h.list = append(h.list, x)
	h.up(len)
}
func (h *Heap) Print() {
	fmt.Println(h.list)
}

/**
 * @description:判断父节点是否小于当前节点
 * @param {int} x
 * @return {*}
 */
func (h *Heap) up(i int) {
	for {
		p := (i - 1) / 2 //寻找父节点
		if i == p || h.cmp(i, p) {
			return
		}
		h.swap(i, p)
		i = p
	}
}

/**
 * @description:
 * @param {int} i
 * @return {*}
 */
func (h *Heap) down(i int) bool {
	old := i
	for {
		c := 2*i + 1 //左孩子
		if c >= len(h.list) {
			break
		}
		if r := c + 1; r < len(h.list) && h.cmp(c, r) {
			c = r //右边孩子
		}
		if h.cmp(c, i) { //比自己孩子要小
			break
		}
		h.swap(i, c)
		i = c
	}
	return i > old
}

/**
 * @description: 弹出
 * @param {*}
 * @return {*}
 */
func (h *Heap) Pop() int {
	if h.IsEmpty() { //为空返回最小值
		return -1 << 31
	}
	return h.Remove(0)
}

/**
 * @description: 判断是否为空
 * @param {*}
 * @return {*}
 */
func (h *Heap) IsEmpty() bool {
	return len(h.list) == 0
}

/**
 * @description: 删除元素
 * @param {int} i
 * @return {*}
 */
func (h *Heap) Remove(i int) int {
	len := len(h.list) - 1
	if i > len {
		return -1 << 31
	}
	if len != i {
		h.swap(i, len)
	}
	v := h.list[len]
	h.list = h.list[:len]
	if !h.down(i) {
		h.up(i)
	}
	return v
}

/**
 * @description: 比较，小顶堆 i > j ，大顶堆相反
 * @param {*} i
 * @param {int} j
 * @return {*}
 */
func (h *Heap) cmp(i, j int) bool {
	if h.isMinHeap {
		return h.list[i] > h.list[j]
	}
	return h.list[i] < h.list[j]
}
func (h *Heap) swap(i, p int) {
	h.list[i], h.list[p] = h.list[p], h.list[i]
}
func NewHeap(isMinHeap bool) *Heap {
	heap := &Heap{
		list:      make([]int, 0),
		isMinHeap: isMinHeap,
	}
	return heap
}

/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.GetMin();
 */
